import entity.TreeNode;

public class LowestCommonAncestorOfBT {
    /*
    * 236. 二叉树的最近公共祖先
    * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
    * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
    * 最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先
    * 且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
    *
    * 树中节点数目在范围 [2, 10^5] 内。
    * -10^9 <= Node.val <= 10^9
    * 所有 Node.val 互不相同 。
    * p != q
    * p 和 q 均存在于给定的二叉树中。
    * */
    public static void main(String[] args){

    }

    // 我的想法：脑袋瓜不是很聪明，没想出来
    public TreeNode mySolution(TreeNode root, TreeNode p, TreeNode q){

        return null;
    }

    // 这里要找最深的共同祖先，当然得从地下开始遍历，且最好是先遍历左右子树
    // 这写法都贴你脸上了，后序遍历啊
    // 找到pq就返回，当第一次出现左右返回值都不为空的时候，说明该节点就是最深公共祖先

    public TreeNode solution(TreeNode root, TreeNode p, TreeNode q){
        if (root == null || root == p || root == q)
            return root;
        // 先下探
        TreeNode left = solution(root.left, p, q);
        TreeNode right = solution(root.right, p, q);
        // 这个东西就是他们的最近公共祖先
        if(left == null && right == null)   // 没找到节点
            return null;
        else if(left != null && right == null)  // 找到1个节点
            return left;
        else if(left == null && right != null)  // 找到1个节点
            return right;
        else
            return root;
    }
}
